package main

import "fmt"

/*
152. 乘积最大子数组
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个32-位 整数。
子数组 是数组的连续子序列。

动态规划表达式

	f(i,b) 从头到第i项的最大（小）连续乘积

动态规划方程

	f(i,0) = max{ f(i-1,0)*nums[i] , f(i-1,1)*nums[i] }
*/
func maxProduct1(nums []int) int {
	var res = nums[0]
	f := make([][2]int, len(nums))
	for i := range nums {
		if i == 0 {
			f[i][0], f[i][1] = nums[i], nums[i]
			continue
		}

		f[i][1] = max(nums[i], max(f[i-1][0]*nums[i], f[i-1][1]*nums[i]))
		f[i][0] = min(nums[i], min(f[i-1][0]*nums[i], f[i-1][1]*nums[i]))
		res = max(f[i][1], res)
	}
	return res
}

/*
优化：f(i,0) = max{ f(i-1,0)*nums[i] , f(i-1,1)*nums[i] }

	空间复杂度 ，只需要前一项
*/
func maxProduct2(nums []int) int {
	var res = nums[0]
	f := [2]int{}
	for i := range nums {
		if i == 0 {
			f[0], f[1] = nums[i], nums[i]
			continue
		}

		f[1], f[0] = max(nums[i], max(f[0]*nums[i], f[1]*nums[i])), min(nums[i], min(f[0]*nums[i], f[1]*nums[i]))
		res = max(f[1], res)
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	nums := []int{-3, -4, -2}
	fmt.Println(maxProduct1(nums))
	fmt.Println(maxProduct2(nums))
}
